home *** CD-ROM | disk | FTP | other *** search
/ Linux Cubed Series 4: GNU Archives / Linux Cubed Series 4 - GNU Archives.iso / gnu / enscript.4 / enscript / enscript-1.4.0 / afmlib / strhash.c < prev    next >
Encoding:
C/C++ Source or Header  |  1996-02-27  |  7.7 KB  |  389 lines
  1. /* 
  2.  * String hash table.
  3.  * Copyright (c) 1995 Markku Rossi.
  4.  *
  5.  * Author: Markku Rossi <mtr@iki.fi>
  6.  */
  7.  
  8. /*
  9.  * This file is part of the AFM library.
  10.  * 
  11.  * This library is free software; you can redistribute it and/or
  12.  * modify it under the terms of the GNU Library General Public
  13.  * License as published by the Free Software Foundation; either
  14.  * version 2 of the License, or (at your option) any later version.
  15.  *
  16.  * This library is distributed in the hope that it will be useful,
  17.  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  18.  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  19.  * Library General Public License for more details.
  20.  *
  21.  * You should have received a copy of the GNU Library General Public
  22.  * License along with this library; if not, write to the Free
  23.  * Software Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  24.  */
  25.  
  26. #include <afmint.h>
  27. #include <strhash.h>
  28.  
  29. /*
  30.  * Types and definitions.
  31.  */
  32.  
  33. #define STRHASH_DEBUG 0
  34.  
  35. #define HASH_SIZE 8192
  36.  
  37. struct hash_list_st
  38. {
  39.   struct hash_list_st *next;
  40.   char *key;            /* malloc()ated copy of key. */
  41.   int keylen;
  42.   void *data;
  43. };
  44.  
  45. typedef struct hash_list_st HashList;
  46.  
  47. typedef HashList *HashTable;
  48.  
  49. typedef struct stringhash_st
  50. {
  51.   HashTable *hash_table;
  52.  
  53.   /* Scan support. */
  54.   unsigned int next_idx;
  55.   HashList *next_item;
  56.  
  57. #if STRHASH_DEBUG
  58.   int items_in_hash;
  59. #endif /* STRHASH_DEBUG */
  60. } *hash_t;
  61.  
  62.  
  63. /*
  64.  * Prototypes for static functions.
  65.  */
  66.  
  67. static int count_hash __P ((const char *key, int keylen));
  68.  
  69.  
  70. /*
  71.  * Global functions.
  72.  */
  73.  
  74. StringHashPtr
  75. strhash_init ()
  76. {
  77.   StringHashPtr tmp;
  78.   
  79.   tmp = (StringHashPtr) calloc (1, sizeof (*tmp));
  80.   if (!tmp)
  81.     return NULL;
  82.  
  83.   tmp->hash_table = (HashTable *) calloc (HASH_SIZE, sizeof (HashTable));
  84.   if (!tmp->hash_table)
  85.     {
  86.       free (tmp);
  87.       return NULL;
  88.     }
  89.   
  90. #if STRHASH_DEBUG
  91.   tmp->items_in_hash = 0;
  92. #endif /* STRHASH_DEBUG */
  93.   return tmp;
  94. }
  95.  
  96.  
  97. void
  98. strhash_free (StringHashPtr hash)
  99. {
  100.   HashList *list, *list_next;
  101.   int i;
  102.  
  103.   if (!hash)
  104.     return;
  105.  
  106.   /* Free chains. */
  107.   for (i = 0; i < HASH_SIZE; i++)
  108.     for (list = hash->hash_table[i]; list; list = list_next)
  109.       {
  110.     list_next = list->next;
  111.     free (list->key);
  112.     free (list);
  113.       }
  114.   
  115.   /* Free hash. */
  116.   free (hash->hash_table);
  117.   free (hash);
  118. }
  119.  
  120.     
  121. int
  122. strhash_put (StringHashPtr hash, char *key, int keylen, void *data, 
  123.          void **old_data)
  124. {
  125.   HashList *list, *prev = NULL;
  126.   int pos, cmp_val;
  127.  
  128.   if (!hash || !key || keylen <= 0)
  129.     return 0;
  130.  
  131.   if (old_data)
  132.     *old_data = NULL;
  133.   pos = count_hash (key, keylen);
  134.  
  135.   /* Is it already here? */
  136.   for (list = hash->hash_table[pos]; list; prev = list, list = list->next)
  137.     if (list->keylen == keylen)
  138.       {
  139.     cmp_val = memcmp (key, list->key, keylen);
  140.     if (cmp_val == 0)
  141.       {
  142.         /* We had an old occurence. */
  143.         if (old_data)
  144.           *old_data = list->data;
  145.         list->data = data;
  146.         return 1;
  147.       }
  148.     else if (cmp_val < 0)
  149.       {
  150.         /* Run over. Correct position is prev->next. */
  151.         break;
  152.       }
  153.       }
  154.     else if (list->keylen > keylen)
  155.       /* Lists are kept sorted so that smallest keys are at the head and
  156.      keys with equal length are in normal sorted order. */
  157.       break;
  158.  
  159.   /* No old data. */
  160.   list = (HashList *) calloc (1, sizeof (HashList));
  161.   if (!list)
  162.     return 0;
  163.   list->key = (char *) malloc (keylen);
  164.   if (!list->key)
  165.     {
  166.       free (list);
  167.       return 0;
  168.     }
  169.  
  170.   memcpy (list->key, key, keylen);
  171.   list->keylen = keylen;
  172.   list->data = data;
  173.   
  174.   /* Insert list to the correct position. */
  175.   if (!prev)
  176.     {
  177.       list->next = hash->hash_table[pos];
  178.       hash->hash_table[pos] = list;
  179.     }
  180.   else
  181.     {
  182.       list->next = prev->next;
  183.       prev->next = list;
  184.     }
  185. #if STRHASH_DEBUG
  186.   hash->items_in_hash++;
  187. #endif /* STRHASH_DEBUG */
  188.   return 1;
  189. }
  190.  
  191.  
  192. int
  193. strhash_get (StringHashPtr hash, const char *key, int keylen, void **data)
  194. {
  195.   HashList *list;
  196.   int pos, cmp_val;
  197.  
  198.   if (!hash || !key || keylen <= 0 || !data)
  199.     return 0;
  200.  
  201.   *data = NULL;
  202.   pos = count_hash (key, keylen);
  203.   for (list = hash->hash_table[pos]; list; list = list->next)
  204.     if (list->keylen == keylen)
  205.       {
  206.     cmp_val = memcmp (key, list->key, keylen);
  207.     if (cmp_val == 0)
  208.       {
  209.         *data = list->data;
  210.         return 1;
  211.       }
  212.     else if (cmp_val < 0)
  213.       /* Run over. */
  214.       break;
  215.       }
  216.     else if (list->keylen > keylen)
  217.       /* Run over. */
  218.       break;
  219.  
  220.   return 0;
  221. }
  222.  
  223.  
  224. int
  225. strhash_delete (StringHashPtr hash, const char *key, int keylen, void **data)
  226. {
  227.   HashList *list, *prev = NULL;
  228.   int pos, cmp_val;
  229.  
  230.   if (!hash || !key || keylen <= 0 || !data)
  231.     return 0;
  232.  
  233.   *data = NULL;
  234.   pos = count_hash (key, keylen);
  235.   for (list = hash->hash_table[pos]; list; prev = list, list = list->next)
  236.     if (list->keylen == keylen)
  237.       {
  238.     cmp_val = memcmp (key, list->key, keylen);
  239.     if (cmp_val == 0)
  240.       {
  241.         /* Value found. */
  242.         if (prev == NULL)
  243.           hash->hash_table[pos] = list->next;
  244.         else
  245.           prev->next = list->next;
  246.         
  247.         *data = list->data;
  248.         free (list->key);
  249.         free (list);
  250.  
  251.         /* Init scan. */
  252.         hash->next_idx = 0;
  253.         hash->next_item = NULL;
  254.  
  255. #if STRHASH_DEBUG
  256.         hash->items_in_hash--;
  257. #endif /* STRHASH_DEBUG */
  258.         return 1;
  259.       }
  260.     else if (cmp_val < 0)
  261.       /* Not found. */
  262.       break;
  263.       }
  264.     else if (list->keylen > keylen)
  265.       /* Run over. */
  266.       break;
  267.  
  268.   return 0;
  269. }
  270.  
  271.  
  272. int
  273. strhash_get_first (StringHashPtr hash, char **key_return,
  274.            int *keylen_return, void **data_return)
  275. {
  276.   if (!hash || !key_return || !keylen_return || !data_return)
  277.     return 0;
  278.  
  279.   for (hash->next_idx = 0; hash->next_idx < HASH_SIZE; hash->next_idx++)
  280.     {
  281.       hash->next_item = hash->hash_table[hash->next_idx];
  282.       if (hash->next_item)
  283.     {
  284.       *key_return = hash->next_item->key;
  285.       *keylen_return = hash->next_item->keylen;
  286.       *data_return = hash->next_item->data;
  287.       return 1;
  288.     }
  289.     }
  290.   return 0;
  291. }
  292.  
  293.  
  294. int
  295. strhash_get_next (StringHashPtr hash, char **key_return,
  296.           int *keylen_return, void **data_return)
  297. {
  298.   if (!hash || !key_return || !keylen_return || !data_return)
  299.     return 0;
  300.  
  301.   for (; hash->next_idx < HASH_SIZE; hash->next_idx++)
  302.     {
  303.       if (hash->next_item == NULL)
  304.     hash->next_item = hash->hash_table[hash->next_idx];
  305.       else
  306.     hash->next_item = hash->next_item->next;
  307.  
  308.       if (hash->next_item)
  309.     {
  310.       *key_return = hash->next_item->key;
  311.       *keylen_return = hash->next_item->keylen;
  312.       *data_return = hash->next_item->data;
  313.       return 1;
  314.     }
  315.     }
  316.   return 0;
  317. }
  318.  
  319.  
  320. #if STRHASH_DEBUG
  321. void
  322. strhash_debug (StringHashPtr hash)
  323. {
  324.   int i, count = 0, max = 0;
  325.   HashList *tmp;
  326.   
  327.   if (!hash)
  328.     {
  329.       fprintf (stderr, "Invalid hash handle!\n");
  330.       return;
  331.     }
  332.   fprintf (stderr, "hash_size\t%d\n", HASH_SIZE);
  333.   fprintf (stderr, "items_in_hash\t%d\n", hash->items_in_hash);
  334.   
  335.   for (i = 0; i < HASH_SIZE; i++)
  336.     if (hash->hash_table[i] == NULL)
  337.       count++;
  338.   fprintf (stderr, "empty entries\t%d\n", count);
  339.  
  340.   count = 0;
  341.   for (i = 0; i < HASH_SIZE; i++)
  342.     {
  343.       for (tmp = hash->hash_table[i]; tmp; tmp = tmp->next)
  344.     count++;
  345.       max = count > max ? count : max;
  346.       count = 0;
  347.     }
  348.   fprintf (stderr, "longest list\t%d\n", max);
  349.  
  350.   if (max > 0)
  351.     {
  352.       /* Print the first longest list. */
  353.       for (i = 0; i < HASH_SIZE; i++)
  354.     {
  355.       count = 0;
  356.       for (tmp = hash->hash_table[i]; tmp; tmp = tmp->next)
  357.         count++;
  358.       if (count == max)
  359.         {
  360.           for (count = 0, tmp = hash->hash_table[i]; tmp;
  361.            tmp = tmp->next, count++)
  362.         {
  363.           fprintf (stderr, "%d\t", count);
  364.           for (i = 0; i < tmp->keylen; i++)
  365.             fprintf (stderr, "%c", tmp->key[i]);
  366.         }
  367.           break;
  368.         }
  369.     }
  370.     }
  371. }
  372. #endif /* STRHASH_DEBUG */
  373.  
  374.  
  375. /*
  376.  * Static functions.
  377.  */
  378.  
  379. static int
  380. count_hash (const char *key, int keylen)
  381. {
  382.   unsigned int val = 0, i;
  383.  
  384.   for (i = 0; i < keylen; i++)
  385.     val = (val << 5) ^ (unsigned char)key[i]
  386.       ^ (val >> 16) ^ (val >> 7);
  387.   return val % HASH_SIZE;
  388. }
  389.